package com.zc.datastructure.structure.tree.binarytree;

import com.zc.datastructure.structure.AbstractNodeData;
import com.zc.datastructure.structure.tree.AbstractTree;
import lombok.Data;
import lombok.EqualsAndHashCode;

/**
 * @author: zhuCan
 * @date: 2019-08-06 15:12
 * @description: 二叉树  ( 有序 )
 */
@EqualsAndHashCode(callSuper = true)
@Data
public class BinaryTree<T extends AbstractNodeData<T>> extends AbstractTree<BinaryNode<T>, T> {

  @Override
  public void insert(T data) {
    //把数据构建成结点
    BinaryNode<T> treeNode = new BinaryNode<>();
    treeNode.setData(data);

    //先遍历 比较大小找到合适的位置再插入
    if (root != null) {
      BinaryNode<T> currentNode = root;
      BinaryNode<T> temp;
      while (true) {
        //暂存 结点
        temp = currentNode;
        //判断 是流向左子结点
        if (currentNode.getData().compareTo(data) > 0) {
          currentNode = currentNode.getLeftChild();
          //到达树的末端 ,就插入结点
          if (currentNode == null) {
            temp.setLeftChild(treeNode);
            return;
          }
          //流向右子结点
        } else {
          currentNode = currentNode.getRightChild();
          //到达树的末端 ,就插入结点
          if (currentNode == null) {
            temp.setRightChild(treeNode);
            return;
          }
        }
      }
    } else {
      //初始 根节点为空 ,则直接把数据创建为根
      root = treeNode;
    }
  }

  @Override
  public BinaryNode<T> get(T data) {
    // 循环迭代 遍历 查找
    BinaryNode<T> currentNode = root;

    while (true) {
      if (currentNode != null) {
        if (currentNode.getData().compareTo(data) == 0) {
          return currentNode;
        } else if (currentNode.getData().compareTo(data) > 0) {
          currentNode = currentNode.getLeftChild();
        } else {
          currentNode = currentNode.getRightChild();
        }
      } else {
        return null;
      }
    }
  }

  /**
   * 删除元素
   * 删除元素如果细分的话，可以分为4中：没有子节点，只有左节点，只有右节点，有两个子节点
   * 1）没有子节点这种情况比较简单，直接删除就可以了
   * 2）只有左节点或右节点，这两种情况处理方式是一致的，只是方向相反，所以在一起讲了，
   * 将删除节点的父节点的左节点（右节点）指向删除节点的子节点，将左节点（右节点）指向删除节点的父节点
   * 3）有两个子节点，这种情况相对来说比较复杂一点：
   * 找到删除节点的前驱节点或后继节点，然后将前驱或后继节点的值赋给删除节点，然后将前驱或后继节点删除。本质是删除前驱或后继节点
   * 前驱节点的特点：
   * 1）删除的左子节点没有右子节点，那么左子节点即为前驱节点
   * 2）删除节点的左子节点有右子节点，那么最右边的最后一个节点即为前驱节点
   * 后继节点的特点：
   * 与前驱节点刚好相反，总是右子节点，或则右子节点的最左子节点;例如：删除节点为c ，那么前驱节点为 m，后继节点为n
   *
   * @param data
   */
  @Override
  public void delete(T data) {
    //先查找到 数据的树节点
    BinaryNode<T> currentNode = root;
    BinaryNode<T> parent = currentNode;
    while (true) {
      if (currentNode != null) {
        if (currentNode.getData().compareTo(data) == 0) {

        } else if (currentNode.getData().compareTo(data) > 0) {
          currentNode = currentNode.getLeftChild();
        } else {
          currentNode = currentNode.getRightChild();
        }
      }
    }
  }

  /**
   * 递归 删除
   *
   * @param node
   */
  private void delete(BinaryNode<T> node) {


  }

  @Override
  public void clear() {

  }

  @Override
  public int height() {
    return 0;
  }

  @Override
  public BinaryNode<T> parent(BinaryNode<T> node) {
    return null;
  }

  /**
   * 先序 遍历
   *
   * @param node
   */
  public void preOrder(BinaryNode<T> node) {
    if (node != null) {
      System.out.println(node.getData());
      preOrder(node.getLeftChild());
      preOrder(node.getRightChild());
    }
  }

  /**
   * 中序 遍历
   *
   * @param node
   */
  public void inOrder(BinaryNode<T> node) {
    if (node != null) {
      inOrder(node.getLeftChild());
      System.out.println(node.getData());
      inOrder(node.getRightChild());
    }
  }

  /**
   * 后序 遍历
   *
   * @param node
   */
  public void postOrder(BinaryNode<T> node) {
    if (null != node) {
      postOrder(node.getLeftChild());
      postOrder(node.getRightChild());
      System.out.println(node.getData());
    }
  }
}
